import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/27 14:49
 * @description 排序 + 优先队列
 */
public class Solution {
    public static void main(String[] args) {
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12},  {15, 20, 10}, {19, 24, 8}};
        Solution solution = new Solution();
        solution.getSkyline(buildings);
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        // 按高度降序排列
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        // 收集端点信息
        List<Integer> bo = new ArrayList<>();
        for (int[] bu: buildings) {
            bo.add(bu[0]);
            bo.add(bu[1]);
        }
        Collections.sort(bo);

        List<List<Integer>> ans = new ArrayList<>();
        int n = buildings.length, index = 0;
        for (int boundary : bo) {
            // 将左端点小于等于边界的区间信息加入优先队列
            while (index < n && buildings[index][0] <= boundary) {
                pq.add(new int[]{buildings[index][1], buildings[index][2]});
                index++;
            }
            // 将右端点小于等于边界的区间删除
            while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
                pq.poll();
            }
            int max = pq.isEmpty() ? 0 : pq.peek()[1];
            if (ans.size() == 0 || max != ans.get(ans.size() - 1).get(1)) {
                // 如果高度与上一点重复了，那么此端点遗弃，不同才添加
                ans.add(Arrays.asList(boundary, max));
            }
        }
        return ans;
    }
}
